The present invention relates to a computing method for 3D graphics. More specifically, the present invention relates to a pixel based fast area-coverage computing method for anti-aliasing in 3D graphics applications.
In the prior art of high-end 3D computer graphics, the pixels of an image are sub-divided into sub-pixels, and an area-coverage computing technique is employed to resolve the aliasing effect common to graphics imaging. That is, an anti-aliasing method is used which assigns pixel colors based on the fraction of the pixel area that is covered by the image being rendered. Various prior art examples of anti-aliasing methods are described in U.S. Pat. No. 4,908,780, by Priem, et al. (1990); and U.S. Pat. No. 5,299,308, by Suzuki, et al. (1994).
For real time anti-aliasing operation in the prior art, the segment based area-coverage computing method is generally used. That is, a set of consecutive pixels on a scan line constitute a segment, which is evaluated as an entity, utilizing existing graphics pipelines within a system, so that no additional hardware is required. However, because the pixel data is accumulated in segments, there are inherent time delays involved, which adversely affect the overall system pixel yield rate.
To illustrate the need for an anti-aliasing technique, FIG. 1 shows a screen geometric of pixels and an aliased triangle image. The dash-lined lattice constitutes the geometric coordinate system for pixels. The geometric center of each pixel is located at the point where the vertical and horizontal dash lines intersect. The solid-lined lattice is appended to indicate the pixels"" shape. Scan lines are horizontal lines which cross the geometric center of the pixels. The scan lines are shown as horizontal dash lines.
In graphics without anti-aliasing, as in FIG. 1, not all of the pixels on the edges are drawn. That is, a pixel is drawn only when it is interior to the edges of the triangle. More specifically, for a pixel on the left edge, it is drawn only if the point where the left edge and scan line intersect is located to the left of the pixel""s geometric center. Similarly, for a pixel on the right edge, a pixel is drawn only if the point where the right edge and scan line intersect is located to the right of the pixel""s geometric center. A pixel on an edge is considered to be covered when it is interior to the edge. For example, pixels A and B in FIG. 1 illustrate the left and right edge cases, respectively, and are considered to be covered. Therefore, for a pixel to be drawn on an aliased triangle, it must be either interior to the triangle, or it must meet one of the edge conditions, as described above. This is the primary rule for determining whether or not a pixel should be drawn on an aliased image.
As a result, the pixel edges are drawn in a staircase fashion, as shown in FIG. 1. The staircase shape is known in the art as xe2x80x9cjaggedxe2x80x9d, and the phenomenon that causes the xe2x80x9cjaggiesxe2x80x9d is called aliasing.
There are two approaches used in the graphics art to suppress the aliasing effect. First, all the pixels that intersect the edge lines, whether covered or not, are taken into account. Second, a pixel is drawn by blending its color (foreground color) with the background color. The amount of blending (ratio of foreground color to background color) is proportional to the pixel""s area that is covered by the edge line. FIG. 2 illustrates the same triangle as in FIG. 1, with the addition of all the xe2x80x9cuncoveredxe2x80x9d pixels that intersect the edge lines. As shown in FIG. 2, the jaggies are reduced. However, a method is required for computing the area-coverage of an edge over a pixel.
Calculating a pixel""s area-coverage may be accomplished by dividing each physical pixel into logical sub-pixels. FIG. 3 depicts an enlargement of the second row of the triangle and pixels shown in FIG. 2. In general, a pixel is divided linearly in both the x-direction and y-direction by a number n, which is a power of two. Accordingly a total of n2 sub-pixels are generated. In FIG. 3, n=4, so that n2=16 sub-pixels for each pixel.
After dividing each pixel into sub-pixels, each sub-pixel is tested to determine whether or not it is interior to the edges. The same edge intersection rule is applied as in the aliased case, described above, except that the test is now run on sub-pixels, rather than on pixels. Testing of the sub-pixels can be implemented without the need for additional hardware, since the same hardware module used for testing pixels can be implemented to test sub-pixels. This is the most commonly used approach in the prior art.
The outcome of each sub-pixel""s test is accumulated in a memory buffer. When all of the sub-pixels of a pixel have been tested, the accumulated test result is retrieved from memory. This accumulated test result represents the area-coverage of the pixel.
In the prior art implementation, the tests must be performed in scan-line order. Consequently, the test operation has to complete all n sub-pixel scan-lines of a segment before the coverage of a pixel is determined. Since the aperture of this type of test operation is the entire segment, this method is categorized as a segment based area-coverage computing algorithm.
In the FIG. 3 example, there are approximately 3xn2 sub-pixels along the path to be tested. Since the computation of area-coverage for each pixel must wait for n sub-pixel scan-lines to be completely tested, delays are introduced into the test operation. As such, the segment based area-coverage method has the disadvantage of slowing down the rate of pixel yield.
Accordingly, it is an object of the present invention to overcome this disadvantage of the prior art by using a pixel based method and apparatus for sub-pixel area-coverage, which does not incur the inherent testing delays of the segment based method.
In accordance with an illustrative embodiment of the present invention, a pixel based method for computing the area-coverage of an image bounded by edges is as follows:
a) selecting a segment of the image to be evaluated for area-coverage, the segment being made up of a set of consecutive pixels on a scan-line section which intersects at least one of the boundary edges,
b) dividing each of the pixels into an n by n sub-pixel array, with n rows and n columns, where n is a number equal to a power of 2, and where the sub-pixel array has n sub-pixel scan-lines, with each sub-pixel scan-line crossing the geometric center of each row of sub-pixels,
c) selecting one of the sub-pixel arrays to constitute a current pixel for area-coverage evaluation,
d) determining the x-axis coordinates of the intersection points of the sub-pixel scan-lines of the current pixel with at least one of the boundary edges of the image,
e) comparing these x-axis coordinates with the x-axis coordinate of the current pixel,
f) determining from this comparison an area-coverage value for each of the sub-pixel rows within the current pixel,
g) accumulating the area-coverage values for all of the sub-pixel rows within the current pixel, and
h) normalizing the accumulated area-coverage values to determine an area-coverage value for the current pixel.
The inventive method described above is implemented in an inventive hardware module which is appended to a conventional graphics rendering engine. The resulting increase in overall system pixel yield rate as compared to the prior art segment based method is more than adequate compensation for the additional cost of the inventive hardware module.
An illustrative embodiment of the present invention is more fully described below in conjunction with the following drawings.